import java.util.Stack;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}
public class MyLinkedList {
    public ListNode head;
    //打印链表
    public void display(){
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display2(ListNode newHead){
        ListNode cur = newHead;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //得到链表长度
    public int size(){
        ListNode cur = this.head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    }

    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (this.head == null){
            this.head = node;
        }
        else{
            ListNode cur = this.head;
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    //查找是否包含关键字key
    public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //前置节点
    public ListNode toFind(int index){
        ListNode cur = this.head;
        for (int i = 0; i <= index - 1; i++){
            cur = cur.next;
        }
        return cur;
    }
    //在任意位置插入节点，下标为index
    public void addIndex(int index, int data){
        ListNode node = new ListNode(data);
        if (index < 0 || index > size()){
            System.out.println("位置不合法");
        }
        else if (index == 0){
            addFirst(data);
        }
        else if (index == size()){
            addLast(data);
        }
        else {
            ListNode cur = toFind(index);
            node.next = cur.next;
            cur.next = node;
        }
    }

    //前置节点的val
    public ListNode prev(int key){
        ListNode cur = this.head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return  null;
    }
    //删除第一次出现的关键字key
    public void remove(int key){
        if (this.head == null){
            System.out.println("单链表为空");
            return;
        }
        if (this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = prev(key);
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //删除所有出现的关键词key
    public void removeAllKey(int key){
        if (this.head == null){
            System.out.println("该链表为空");
            return;
        }
        ListNode prev = this.head;
        ListNode cur = prev.next;
        while (prev.next != null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }
            else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (this.head.val == key){
            this.head = this.head.next;
        }
    }

    //清空链表
    public void clear(){
        while (this.head != null) {
            ListNode cur = this.head.next;
            this.head.next = null;
            this.head = cur;
        }
    }

    //反转一个单链表
    public ListNode charge(){
        if (head == null){
            return null;
        }
        ListNode headed = this.head;
        ListNode prev = this.head;
        ListNode cur = prev.next;
        ListNode curNext = prev.next;
        while (cur != null){
            curNext = curNext.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        headed.next = null;
        return prev;
    }

    //返回链表的中间节点，如果有两个则返回第二个
    public ListNode middleNode(ListNode head){
        ListNode fast = this.head;
        ListNode slow = this.head;
        if (head == null){
            return null;
        }
        while (fast != null || fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个节点
    public ListNode FindKthToTail(ListNode head,int k){
        if (k < 0 || this.head == null){
            return null;
        }
        ListNode first = this.head;
        ListNode second = this.head;
        while (k - 1 != 0){
            if (first.next == null){
               return null;
            }
            first = first.next;
            k--;
        }
        while (first.next != null){
            first = first.next;
            second = second.next;
        }
        return second;
    }

    //将两个有序链表合为一个新的有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode mode = new ListNode(-1);
        ListNode start = mode;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                mode.next = list1;
                list1 = list1.next;
                mode = mode.next;
            } else {
                mode.next = list2;
                list2 = list2.next;
                mode = mode.next;
            }
        }
        if (list1 == null) {
            mode.next = list2;
        }
        else {
            mode.next = list1;
        }
        return start.next;
    }

    //编写代码，以给定值x为基准，小于X的节点排在大于或等于X节点之前
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }
            else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;

                }
            }
            cur = cur.next;
        }
            if (bs == null){
                return as;
            }
            be.next = as;
            if (as != null) {
                ae.next = null;
            }
            return bs;
        }

    //在一个排序的列表中，存在重复节点，删除所有重复节点
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                tmp.next = cur;
                cur = cur.next;
                tmp = tmp.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }

    //链表的回文结构
    public boolean chkPalindrome(ListNode head){
        if (head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //找中间节点
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //翻转后半部分
        ListNode cur = slow.next;
        while (cur != null){
            ListNode newNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = newNext;
        }
        //当节点个数为奇数时
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
            //当节点个数为偶数时
            if (head == slow.next){
                return true;
            }
        }
        return true;
    }

    //输入两个链表，找出他们的第一个公共节点
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB){
         if(headA == null || headB == null){
             return null;
         }
         //获取两个链表的长度
         ListNode pl = headA;
         ListNode ps = headB;
         int lenA = 0;
         int lenB = 0;
         while (pl != null){
             lenA++;
             pl = pl.next;
         }
         pl = headA;
         while (ps != null){
             lenB++;
             ps = ps.next;
         }
         ps = headB;
         int len = lenA - lenB;//差值步
         if (len < 0){
             pl = headB;
             ps = headA;
             len = lenB - lenA;
         }
         //判断公共节点,长链表先走len步
        while (len != 0){
            pl = pl.next;
            len--;
        }
        //两个链表一起走
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

    //给定一个链表判定是否有环
    public boolean hasCycle(ListNode head){
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    //返回链表开始入环的第一个节点
    public ListNode detectCycle(ListNode head){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                while (cur != slow){
                    cur = cur.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

    //链表两数相加(这个代码有问题）
    public ListNode addTwoNumbers(ListNode A, ListNode B) {
        //构建新链表的头节点
        ListNode node = new ListNode(0);
        ListNode cur = node;
        //进位
        int tmp = 0;
        //当两个链表都遍历完且进位完再跳出循环
        while (A != null || B != null || tmp != 0) {
            //得到两个链表的值
            int AVal = A != null ? A.val : 0;
            int BVal = B != null ? B.val : 0;
            //构建新链表的下一个节点
            node.next = new ListNode((tmp + AVal + BVal) % 10);
            node = node.next;
            //进位
            tmp = (tmp + AVal + BVal) / 10;
            //两个链表后移至下个节点继续遍历
            if (A.next != null) {
                A = A.next;
            }
            if (B.next != null) {
                B = B.next;
            }
        }
        return cur.next;
    }


    //删除所有元素，使得重复元素只出现一次
    public ListNode deleteDuplicates1(ListNode head){
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null){
            if (prev.val != cur.val){
                cur = cur.next;
                prev = prev.next;
            }
            else {
                cur = cur.next;
                prev.next = cur;
            }
        }
        return head;
    }

    //链表的回文结构(印象中吧应该是第二次写了）
    public boolean isPalindrome(ListNode head){
        if (head == null){
            return false;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        ListNode curNext = null;
        while (cur != null){
            curNext = cur.next;
            cur.next =slow;
            slow = cur;
            cur = curNext;
        }
        ListNode newHead = this.head;
        while (newHead != slow){
            if (newHead.val == slow.val){
                if (newHead.next == slow){
                    return true;
                }
                newHead = newHead.next;
                slow = slow.next;
            }
            else {
                return false;
            }
        }
        return true;
    }


    //从尾到头反过来返回每个节点的值（用数组返回）
    public int[] reversePrint(ListNode head){
        int[] array = new int[0];
        if (head == null){
            return array;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        int i = 0;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
            i++;
        }
        i++;
        int[] array2 = new int[i];
        head.next = null;
        head = prev;
        int j = 0;
        while (head != null){
            array2[j] = head.val;
            head = head.next;
            j++;
        }
        return array2;
    }

    //删除对应节点的值
    public ListNode deleteNode(ListNode head, int val){
        if (head == null){
            return null;
        }
        ListNode prev = head;
        ListNode cur= head.next;
        //如果要删除的节点不是头节点和尾节点
        while (cur != null){
            if (cur.val == val){
                prev.next = cur.next;
                //如果是尾节点
                if (cur.next == null){
                    prev.next = null;
                }
            }
            prev = cur;
            cur = cur.next;
        }
        //要删除的节点是头节点
        if (head.val == val){
            head = head.next;
        }
        return head;
    }

    //返回倒数第K个节点
    public ListNode getKthFromEnd(ListNode head, int k){
        if (head == null){
            return null;
        }
        ListNode cur = head;
        ListNode prev = head;
        while (k - 1 != 0 ){
            cur = cur.next;
            k--;
        }
        while (cur.next != null){
            cur = cur.next;
            prev = prev.next;
        }
        return prev;
    }

    //链表的反转
    public ListNode reverseList(ListNode head){
        if (head == null){
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur= curNext;
        }
        head.next = null;
        head = prev;
        return head;
    }

    //合并两个排序的链表
    public ListNode mergeTwoLists1(ListNode headA, ListNode headB){
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while (headA != null && headB != null){
            if (headA.val <= headB.val){
                cur.next = headA;
                headA = headA.next;
                cur = cur.next;
            }
            else {
                cur.next = headB;
                headB = headB.next;
                cur = cur.next;
            }
        }
        if (headA == null){
            cur.next = headB;
        }
        else {
            cur.next = headA;
        }
        return newHead.next;
    }


    //找到第一个公共节点
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if (headA == null || headB == null){
            return null;
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int i = 1;
        int j = 1;
        while (cur1 != null){
            cur1 = cur1.next;
            i++;
        }
        while (cur2 != null){
            cur2 = cur2.next;
            j++;
        }
        if (i < j){
            int tmp = i;
            i = j;
            j = tmp;
        }
        int size = i - j;
        cur1 = headA;
        cur2 = headB;
        if (i > j){
            while (size != 0){
                cur1 = cur1.next;
                size--;
            }
        }
        else  {
            while (size != 0){
                cur2 = cur2.next;
                size--;
            }
        }
        while (cur1 != null && cur2 != null){
            if (cur1 == cur2){
                return cur1;
            }
            else {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return null;
    }

    //反转链表
    public ListNode reverseList1(ListNode head){
        if (head == null){
            return null;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        ListNode curNext = cur;
        while (cur != null){
            curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        head.next = null;
        head = prev;
        return head;
    }

    //返回倒数第K个节点，给定的k保证是有效的
    public int kthToLast(ListNode head, int k){
        ListNode fast = head;
        ListNode slow = head;
        //先让fast走k - 1步
        while (k - 1 != 0){
            fast = fast.next;
            k--;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    //删除中间节点
    public void deleteNode(ListNode node){
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != node){
            prev = prev.next;
            cur = cur.next;
        }
        prev.next = cur.next;
    }

    //移除重复节点，保留一个
    public ListNode removeDuplicateNodes(ListNode head){
       if (head == null || head.next == null){
           return head;
       }
       ListNode newHead = head;
       ListNode prev = null;
       ListNode cur = null;
       while (newHead != null){
           prev = newHead;
           cur = newHead.next;
           while (cur != null){
               if (cur.val != newHead.val){
                   cur = cur.next;
                   prev = prev.next;
               }
               else {
                  prev.next = cur.next;
                  cur = prev.next;
               }
           }
           newHead = newHead.next;
       }
       return head;
    }

    //二进制链表转整数
    public int getDecimalValue(ListNode head){
        ListNode cur = head;
        int a = 0;
        while (cur != null){
            a = a << 1;
            a = a + cur.val;
            cur = cur.next;
        }
        return a;
    }

    //两数相加
    public ListNode addTwoNumbers1(ListNode headA, ListNode headB){
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        int tmp = 0;
        while (headA != null || headB != null){
            int x = headA == null ? 0 : headA.val;
            int y = headB == null ? 0 : headB.val;
            int sum = x + y + tmp;
            tmp = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            if (headA != null){
                headA = headA.next;
            }
            if (headB != null){
                headB = headB.next;
            }
        }
        if (tmp == 1){
            cur.next = new ListNode(tmp);
        }
        return pre.next;
    }

    //删除链表中倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        if (n == 0){
            while (fast.next != null){
                cur = fast;
                fast = fast.next;
            }
            cur.next = null;
        }
        else {
            while (n - 1 != 0){
                fast = fast.next;
                n--;
            }
            while (fast.next != null){
                cur = slow;
                fast = fast.next;
                slow = slow.next;
            }
            if (cur == slow){
                head = head.next;
            }
            cur.next = slow.next;
        }
        return head;
    }

    //两两交换链表中的节点
    public ListNode swapPairs(ListNode head){
        if (head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = slow.next;
        ListNode pre = null;
        while (fast != null){
            if (slow == head){
                head = fast;
            }
            slow.next = fast.next;
            fast.next = slow;;
            if (slow.next != null){
                pre = slow;
                slow = slow.next;
                fast = slow.next;
                if (slow.next != null) {
                    pre.next = fast;
                }
            }
            else {
                break;
            }
        }
        return head;
    }

    //旋转链表
    public ListNode rotateRight(ListNode head, int k){
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        int count = 0;
        if (head == null){
            return null;
        }
        //判断链表大小
        while (pre != null){
            count++;
            pre = pre.next;
        }
        if (k > count) {
            k = k % count;
        }
        if (k == 0 || k == count || head.next == null){
            return head;
        }
        pre = head;
        //fast先走k - 1 步
        while (k - 1 != 0){
            fast = fast.next;
            k--;
        }
        while (fast.next != null){
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        fast.next = head;
        return slow;
    }

    //删除所有重复的节点，包括本身
    public ListNode deleteDuplicates(ListNode head){
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode slow = pre.next;
        ListNode fast = slow.next;
        //先判断头节点
        if (head.val == slow.val) {
            while (head.val == slow.val) {
                slow = slow.next;
            }
            head = slow;
        }
            if (slow.next != null) {
                slow = slow.next;
                fast = slow.next;
                pre = head;
            }
        else {
            return head;
        }
        //判断中间节点
        while (fast != null){
            if (slow.val == fast.val){
                if (fast.next == null){
                    slow.next = null;
                    return head;
                }
                else {
                    pre.next = fast.next;
                    slow = pre.next;
                    fast = slow.next;
                }
            }
            else {
                fast = fast.next;
                slow = slow.next;
                pre = pre.next;
            }
        }
        return head;
    }

    //分割链表
    public ListNode partition1(ListNode head, int x){
        if (head == null){
            return null;
        }
        ListNode newHead1 = new ListNode(-1);
        ListNode newHead2 = new ListNode(-2);
        ListNode pre1 = newHead1;
        ListNode pre2 = newHead2;
        ListNode cur = head;
        while (cur != null){
            if (cur.val < x){
                pre1.next = cur;
                cur = cur.next;
                pre1 = pre1.next;
            }
            else {
                pre2.next = cur;
                cur = cur.next;
                pre2 = pre2.next;
            }
        }
        pre1.next = newHead2.next;
        pre2.next = null;
        return newHead1.next;
    }

    //合并两个排序的链表
    public ListNode Merge(ListNode headA,ListNode headB){
        if (headA == null){
            return headB;
        }
        if (headB == null){
            return headA;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while (curA != null && curB != null){
            if (curA.val < curB.val){
                cur.next = curA;
                cur = cur.next;
                curA = curA.next;
            }
            else {
                cur.next = curB;
                cur = cur.next;
                curB = curB.next;
            }
        }
        if (curA == null){
            cur.next = curB;
        }
        if (curB == null){
            cur.next = curA;
        }
        return newHead.next;
    }

    //返回倒数第k个链表
    public ListNode FindKthToTail1 (ListNode pHead, int k){
        int count = 0;
        ListNode cur = pHead;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        if (count < k){
            return null;
        }
        if (pHead == null || k == 0){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        for (int i = 0; i < k - 1; i++){
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //删除链表
    public ListNode deleteDuplicates2 (ListNode head){
        if (head == null){
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null){
            if(pre.val == cur.val){
                pre.next = cur.next;
                cur = cur.next;
            }
            else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return head;
    }

    //是否有环
    public boolean hasCycle1(ListNode head){
        if (head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            if (fast == slow){
                return true;
            }
            else {
                fast = fast.next.next;
                slow = slow.next;
            }
        }
        return false;
    }

    //判断第一个公共节点
    public static ListNode getIntersectionNode2(ListNode PHead1, ListNode PHead2){
        if (PHead1 == null || PHead2 == null){
            return null;
        }
        ListNode curA = PHead1;
        ListNode curB = PHead2;
        int k1 = numBer(PHead1);
        int k2 = numBer(PHead2);
        int k = 0;
        if (k1 > k2){
            k = k1 - k2;
            for (int i = 0; i < k; i++){
                curA = curA.next;
            }
        }
        else {
            k = k2 - k1;
            for (int i = 0; i < k; i++){
                curB = curB.next;
            }
        }
        while (curA != curB){
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
    public static int numBer(ListNode head){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //删除链表中倒数第N个节点
    public ListNode removeNthFromEnd1 (ListNode head, int n){
        if(head == null){
            return null;
        }
        if (n == 0){
            return head;
        }
        ListNode slow = head;
        ListNode fast = findN(head, n);
        ListNode pre = slow;
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        if (slow == head){
            return head.next;
        }
        else {
            pre.next = slow.next;
            return head;
        }
    }
    //先走n - 1步
    public ListNode findN(ListNode head, int n){
        ListNode fast = head;
        for (int i = 0; i < n - 1; i++){
            fast = fast.next;
        }
        return fast;
    }

    //删除链表中所有重复的节点
    public ListNode deleteDuplicates3 (ListNode head){
        ListNode newHead  = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = head;
        while (cur != null) {
            if  (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                tmp.next = cur;
                tmp = cur;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }

    //找到链表环的入口节点
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if (pHead == null){
            return null;
        }
        //先判断是否有环
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                slow = pHead;
                while (fast != slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    //链表内指定区间反转
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null){
            return null;
        }
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode pre = newHead;
        for (int i = 0; i < m - 1; i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode kin = null;
        for (int i = 0; i < m - n; i++){
            kin = cur.next;
            cur.next = kin.next;
            kin.next = pre.next;
            pre.next = kin;
        }
        return  newHead.next;
    }

    //递归逆序打印单链表
    public void funDisplay(ListNode head){
        if (head != null){
            funDisplay(head.next);
            System.out.println(head.val);
        }
    }

    //利用栈逆序打印链表
    public void funcDisplay(ListNode head){
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        while (!stack.empty()){
            System.out.print(stack.pop() + " ");
        }
    }

    //给定一个链表，按升序进行排序
    public ListNode merge(ListNode pHead1, ListNode pHead2){
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while (pHead1 != null && pHead2 != null){
            if (pHead1.val < pHead2.val){
                cur.next = pHead1;
                cur = cur.next;
                pHead1 = pHead1.next;
            }
            else {
                cur.next = pHead2;
                cur = cur.next;
                pHead2 = pHead2.next;
            }
        }
        if (pHead1 != null){
            cur.next = pHead1;
        }
        else {
            cur.next = pHead2;
        }
        return newHead.next;
    }
    public ListNode sortInList (ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode mid = head.next;
        ListNode slow = head;
        ListNode fast = head.next.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            mid = mid.next;
            fast = fast.next.next;
        }
        slow.next = null;
        return merge(sortInList(head), sortInList(mid) );
    }
}


























